package com.algorithm;

import java.util.Random;

/**
 * 二分搜寻法（搜寻原则的代表）
 * 说明如果搜寻的数列已经有排序，应该尽量利用它们已排序的特性，以减少搜寻比对的次数，
 * 这是搜寻的基本原则，二分搜寻法是这个基本原则的代表。
 * 解法在二分搜寻法中，从数列的中间开始搜寻，如果这个数小于我们所搜寻的数，由于数列
 * 已排序，则该数左边的数一定都小于要搜寻的对象，所以无需浪费时间在左边的数；如果搜寻
 * 的数大于所搜寻的对象，则右边的数无需再搜寻，直接搜寻左边的数。
 * 所以在二分搜寻法中，将数列不断的分为两个部份，每次从分割的部份中取中间数比对，例如
 * 要搜寻92于以下的数列，首先中间数索引为(0+9)/2 = 4（索引由0开始）：
 * [3 24 57 57 67 68 83 90 92 95]
 * 由于67小于92，所以转搜寻右边的数列：
 * 3 24 57 57 67 [68 83 90 92 95]
 * 由于90小于92，再搜寻右边的数列，这次就找到所要的数了：
 * 3 24 57 57 67 68 83 90 [92 95]
 * <p>
 * 最好最坏空间复杂度为O(1) 因为只用到了固定数目的变量,所以空间复杂度不随输入规模变化
 * 最好时间复杂度为O(1) 即 第一次就找到了
 * 最坏复杂度为O(logN) 即寻找元素在数组的两边的情况,
 * 因为每次查找搜索空间减半，假设输入规模是n，那么下一次搜索规模是n/2,然后是n/4,...,直到n/(2^k) 为1 为止，
 * 这就是最坏情况啦，也就是最多查找k 次，
 * 此时令 n = 2^k,就可以得到最坏时间复杂度为k = O(logn)，其中log 以2 为底。
 * 参考第地址http://blog.csdn.net/frances_han/article/details/6458067
 * Created by houjinxin on 16/3/16.
 */
public class BinarySearch {

    public static int length = 10;
    //数组用于存储
    public static Integer[] array;

    public static Integer[] createArray() {
//        array = new Integer[length];
//        Random random = new Random();
//        for (int i = 0; i < array.length; i++) {
//            array[i] = random.nextInt(length);
//        }
        array = new Integer[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
        return array;
    }

    public static void sort() {
        maopao();
    }

    /**
     * 调换两个元素的位置
     *
     * @param i 元素索引
     * @param j 元素索引
     */
    public static void swap(int i, int j) {
        Integer temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 这是错误的做法, 这里只是调换了两个入参但是对数组没有任何影响
     *
     * @param a
     * @param b
     */
    public static void swap(Integer a, Integer b) {
        Integer temp = a;
        a = b;
        b = temp;
    }

    public static void maopao() {
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (array[i] > array[j]) {
//                    swap(array[i], array[j]);
                    swap(i, j);
                }
            }
        }
    }

    /**
     * 返回指定元素的索引
     *
     * @param num
     * @return 返回指定元素的索引
     */
    public static int binarySearch(Integer num) {

        int midIndex, lower = 0, upper = length - 1;
        while (lower <= upper) {
            midIndex = (lower + upper) / 2;
            if (num > array[midIndex]) { //在中间元素左边
                lower = midIndex + 1;
            } else if (num > array[midIndex]) { //在中间元素右边
                upper = midIndex - 1;
            } else {
                System.out.println(midIndex);
                return midIndex;
            }
        }
        return -1;
    }

    public static int binarySearch2(Integer find) {
        int mid = -1, lower = 0, upper = length - 1;
        while (lower <= upper) {
            mid = (lower + upper) / 2;
            if (find < array[mid]) { //在左边
                upper = mid - 1;
            } else if (find > array[mid]) { //在右边
                lower = mid + 1;
            } else { //查找的元素与中间元素的索引相同
                return mid;
            }
        }
        return mid;

    }

    /**
     *
     * @param find
     * @return
     */
    public static int binarySearch3(int find) {
        int index = -1;
        int lower = 0, upper = array.length - 1;
        while (lower <= upper) {
//            int mid = (lower + upper) / 2;
            int mid = (int) Math.round(lower + 0.618 * (upper - lower));
            System.out.printf("lower:%1$d,upper:%2$d,mid:%3$d\r\n",lower,upper,mid);
            if (array[mid] == find) {
                index = mid;
                break;
            } else if (array[mid] > find) {//upper和lower,不可以取mid 若要查找一个不存在的值,将会出现死循环
                upper = mid - 1;
            } else {
                lower = mid + 1;
            }
        }
        return index;
    }

    public static void printArray() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (Integer num : array) {
            sb.append(num + ",");
        }
        System.out.println(sb.substring(0, sb.length() - 1) + "]");
    }

    public static void main(String[] args) throws InterruptedException {
        long begin = System.currentTimeMillis();
//        long begin = System.nanoTime();
        createArray();
        printArray();
        Integer find = 11;
        sort();
        printArray();
        System.out.println("find的索引是" + binarySearch3(find));
//        long end = System.nanoTime();
//        Thread.sleep(1000);
        long end = System.currentTimeMillis();
        System.out.println("begin:" + begin + "end:" + end + "共耗时" + (end - begin));
    }

}
